﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <string>

using namespace std;

//给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
//
//注意：如果对空文本输入退格字符，文本继续为空。

class Solution
{
public:
    bool backspaceCompare(string s, string t)
    {
        return backspaceCompare(s) == backspaceCompare(t);
    }
    string backspaceCompare(string& s)
    {
        string ret;// ⽤数组模拟栈结构
        for (auto ch : s)
        {
            if (ch != '#') ret += ch;
            else
            {
                if (ret.size()) ret.pop_back();
            }
        }

        return ret;
    }
};

//给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
//
//在 S 上反复执行重复项删除操作，直到无法继续删除。
//
//在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
class Solution
{
public:
    string removeDuplicates(string s)
    {
        string ret;// 搞⼀个数组，模拟栈结构即可
        for (auto ch : s)
        {
            if (ret.size() == 0 || ret.back() != ch) ret += ch;// 出栈
            else ret.pop_back();// ⼊栈
        }

        return ret;

    }
};


//给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
//
//注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
class Solution
{
public:
    string multiply(string s1, string s2)
    {
        //         计算两数相乘的时候，先不考虑进位，等到所有结果计算完毕之后，再去
        // 考虑进位
                // 解法：⽆进位相乘后相加，然后处理进位
        int m = s1.size(), n = s2.size();
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());

        // 1. ⽆进位相乘后相加
        vector<int> tmp(m + n - 1);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                tmp[i + j] += (s1[i] - '0') * (s2[j] - '0');

        // 2. 处理进位
        string ret;
        int cur = 0, carry = 0;
        while (cur < m + n - 1 || carry)
        {
            if (cur < m + n - 1)
            {
                carry += tmp[cur++];
            }

            ret += (carry % 10) + '0';
            carry /= 10;
        }

        // 3. 处理前导零
        while (ret.size() > 1 && ret.back() == '0') ret.pop_back();

        reverse(ret.begin(), ret.end());

        return ret;
    }
};

//给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
class Solution
{
public:
    string addBinary(string a, string b)
    {
        string ret;
        int cur1 = a.size() - 1, cur2 = b.size() - 1, carry = 0;
        while (cur1 >= 0 || cur2 >= 0 || carry)
        {
            if (cur1 >= 0) carry += a[cur1--] - '0';
            if (cur2 >= 0) carry += b[cur2--] - '0';
            ret += (carry) % 2 + '0';
            carry /= 2;
        }

        // 处理前导零
        while (ret.size() > 1 && ret.back() == '0') ret.pop_back();
        reverse(ret.begin(), ret.end());
        return ret;
    }
};


//给你一个字符串 s，找到 s 中最长的回文子串。
//
//如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
class Solution
{
public:
    string longestPalindrome(string s)
    {
        int begin = 0, len = 0;
        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            // 中⼼扩展算法
            // 奇数⻓度的扩展
            int left = i, right = i;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                --left;
                ++right;
            }
            if (right - left - 1 > len)
            {
                begin = left + 1;
                len = right - left - 1;
            }
            // 偶数⻓度的扩展
            left = i, right = i + 1;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                --left;
                ++right;
            }
            if (right - left - 1 > len)
            {
                begin = left + 1;
                len = right - left - 1;
            }
        }

        return s.substr(begin, len);
    }
};

//编写一个函数来查找字符串数组中的最长公共前缀。
//
//如果不存在公共前缀，返回空字符串 ""。
class Solution
{
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        // 我们可以先找出前两个的最⻓公共前缀，然后拿这个最⻓公
        // 共前缀依次与后⾯的字符串⽐较，这样就可以找出所有字符串的最⻓公共前缀
        string ret = strs[0];
        for (int i = 1; i < strs.size(); i++)
        {
            ret = findCommon(ret, strs[i]);
        }

        return ret;
    }
    string findCommon(string& s1, string& s2)
    {
        int i = 0;
        while (i < s1.size() && i < s2.size() && s1[i] == s2[i]) i++;

        return s1.substr(0, i);
    }
};

class Solution
{
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        for (int i = 0; i < strs[0].size(); i++)
        {
            // 统⼀⽐较
            char tmp = strs[0][i];
            for (int j = 1; j < strs.size(); j++)
            {
                if (j == strs.size() || tmp != strs[j][i])
                    return strs[0].substr(0, i);
            }
        }

        return strs[0];
    }
};
int main()
{
	return 0;
}